public class CanPartition {
    // https://leetcode.cn/problems/partition-equal-subset-sum/description/
    class Solution {
        public boolean canPartition(int[] nums) {

            int n = nums.length;
            if(n == 1) return false;
            int [] a = new int[n + 1];
            int sum = 0;
            for(int i = 0 ; i < n ; i ++)
            {
                a[i + 1] = nums[i];
                sum += nums[i];
            }
            if(sum % 2 != 0) return false;
            // dp[i][j] : 表示从前（1-i）个数中挑选某些数，在体积为j的情况下所能放入的最大值

            int target = sum / 2;
            int [][] dp = new int [n+1][target + 2];

            for(int i = 1 ; i <= n ; i ++)
            {
                for(int j = 1 ; j <= target ; j ++ )
                {
                    dp[i][j] = dp[i-1][j];
                    if(j >= a[i])
                    {
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j-a[i]] + a[i]);
                    }
                }
            }

            return dp[n][target] == target;

        }
    }
}
